Round Overview
Discuss this match
After first i days, you can’t be higher than i \cdot A because you can’t ascend faster. Similarly, you can’t be higher than (N - i) \cdot B because you must be able to descend to 0 in N-i remaining days. Since there are no other limitations, any height not greater than min(i \cdot A, (N - i) \cdot B) can be obtained after first i days. We can iterate over i and find a day with the maximum value of mentioned formula min(i \cdot A, (N - i) \cdot B).
1
2
3
4
5
6
7
8
public int maxHeight(int N, int A, int B) {
int ans = 0;
for (int i = 1; i <= N - 1; ++i) {
int maybe = min(i * A, (N - i) * B);
ans = max(ans, maybe);
}
return ans;
}
It’s helpful to notice that we can write the formula for S as: S(X) = X + \lfloor \frac X {10} \rfloor + \lfloor \frac X {100} \rfloor + \ldots. Now it becomes obvious that the function S(X) is strictly increasing (because every component like \lfloor \frac X {10} \rfloor is increasing).
So we want to find such x that f(x) = y for some particular y. It’s a standard problem for increasing functions, for which we can binary search the value x. In the code you will need the function to calculate f(x), i.e. the function for finding S.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long f(long X) {
long S = 0;
while (X > 0) {
S += X;
X /= 10;
}
return S;
}
public long findX(long S) {
// binary search
long low = 1, high = 1000000000 L * 1000000000;
while (low < high) {
long mid = (low + high) / 2;
if (f(mid) < S) low = mid + 1;
else high = mid;
}
if (f(low) == S) return low;
return -1;
}
FromToDivisibleDiv2
Problem Details
The Div1 version of this problem was a bit harder, with N up to 10^9 and M up to 1000. It turns out that the solution there is extremely short, so I recommend you to solve it or check the editorial: FromToDivisible.
TODO, describe an O(n \cdot m) intended solution for this version.
Let t[i] denote numbers chosen by wolves.
If N is even, the xor of all x[i] is equal to the xor of all t[i]. If N is odd, the xor of all x[i] must be equal to 0 (otherwise return -1). For odd N the xor of all t[i] can be any number you want, independently on values of given x[i].
To get easier implementation, consider each of 30 bits separately. For each bit, there is some number of already fixes zeros and ones, and some number of unknown values. To solve the problem fast, you don’t have to think about any complicated formulas.
If all bits were known and we were given the xor of all numbers \text{xor_all}, we would be able to find the sum of numbers (note that t[i] = \text{xor_all} \oplus x[i]). To use this fact, let’s iterate over the value of \text{xor_all} (it is 0 or 1 because we consider only one bit) and over the number of unknown bits replaced with ones. After that, we have everything needed for computing the possible sum. See the comments in the implementation below in case of doubts.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public long minSum(int[] x) {
int n = x.length;
long answer = 0;
for (int which = 0; which < 30; ++which) {
int a0 = 0, a1 = 0, unknown = 0;
for (int i = 0; i < n; ++i) {
if (x[i] == -1) unknown++;
else if ((x[i] & (1 << which)) > 0) a1++;
else a0++;
}
int best = -1;
for (int i = 0; i <= unknown; ++i) {
int zeros = a0 + i;
int ones = a1 + (unknown - i);
// for odd N we need the xor of x[i] to be equal to 0
// so, there must be even number of ones
if (n % 2 == 1 && ones % 2 == 1) continue;
// iterate over xor_all (the xor of t[i])
for (int xor_all = 0; xor_all <= 1; ++xor_all) {
// for even N we want xor_all to be equal to the xor of x[i]
if (n % 2 == 0 && xor_all != ones % 2) continue;
// remember that t[i] = xor_all ^ x[i]
// if xor_all is 1, all zeros are flipped to ones
int maybe = (xor_all == 1) ? zeros : ones;
if (best == -1 || maybe < best) best = maybe;
}
}
if (best == -1) return -1;
answer += ((long) best) << which;
}
return answer;
}
FromToDivisible
Problem Details
The intended solution is very simple but there are some harder approaches, and this is why the problem was used as the medium one.
The solution is to run BFS on M vertices b[0], b[1], \ldots, b[M-1]. Being in a vertex b[i] in BFS means that all multiples of b[i] are reached in the original graph with N vertices.
The starting vertices are those to which we can get from S using one road. I.e. those for which S is divisible by a[i].
In our BFS we can move from b[i] to b[j] if there is some number divisible by both b[i] and a[j]. From such a number there are indeed roads to all multiples of b[j]. To check “if there is a number divisible by both b[i] and a[j]”, we can find the least such number i.e. LCM(b[i], a[j]) and check if it doesn’t exceed N.
We finish the BFS immediately if we reached such b[i] that T is divisible by b[i] (because it means we reached T in the original graph).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// time complexity: O(m^2 * log(10^9))
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
long lcm(int a, int b) {
return (long) a * b / gcd(a, b);
}
public int shortest(int n, int s, int t, int[] a, int[] b) {
int m = a.length;
LinkedList < Integer > obj = new LinkedList < > ();
int dist[] = new int[m];
for (int i = 0; i < m; ++i)
if (s % a[i] == 0) {
dist[i] = 1;
obj.add(i);
}
while (!obj.isEmpty()) {
int i = obj.removeFirst();
if (t % b[i] == 0) return dist[i];
for (int j = 0; j < m; ++j)
if (dist[j] == 0 && lcm(b[i], a[j]) <= n) {
dist[j] = dist[i] + 1;
obj.add(j);
}
}
return -1;
}
There are a few cases and the intended solution considers them separately. Except for performing only one operation, the cases are:
TODO, other cases.
Since the last case may be the hardest one, let’s focus on it. In O(n^4) we can iterate over all subrectangles in the grid. We should consider every subrectangle as a possible intersection of two squares. Without the loss of generality, let’s say its height is greater than its width. Also, let’s say that the smaller square is more on the right. Then, after fixing a rectangle we know exactly where the smaller square is. What we also need, is the best square such that its right side contains the right side of the rectangle. As usually, we can solve it with the dynamic programming. It’s very important to notice that in such DP we don’t have to care about what is in the rectangle. If we assumed it is higher than wider, all squares “with right side containing the right side of rectangle” completely contain the rectangle. So, we just need a square with the biggest improvement of the score if we chose it (the number of zeros minus the number of ones). One way to find such a square is to precompute maxChangeRight[i][j][s] denoting the best improvement of score among squares with upper-left corner in (i,j) with size AT LEAST s.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
final int INF = 1000123;
int n, input[][];
void turn90() {
int tmp[][] = new int[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
tmp[i][j] = input[j][n - 1 - i];
input = tmp;
}
int pref_ones[][]; // the prefix sum of 1's (watch out! the array is 1-based)
int rect_ones(int x1, int y1, int x2, int y2) { // the number of 1's in rectangle
return pref_ones[x2 + 1][y2 + 1] - pref_ones[x1][y2 + 1] -
pref_ones[x2 + 1][y1] + pref_ones[x1][y1];
}
int rect_zeros(int x1, int y1, int x2, int y2) {
return (x2 - x1 + 1) * (y2 - y1 + 1) - rect_ones(x1, y1, x2, y2);
}
int rect_change(int x1, int y1, int x2, int y2) { // how much score would improve
return rect_zeros(x1, y1, x2, y2) - rect_ones(x1, y1, x2, y2);
}
// sq_ones() is the number of 1's in square of size s with upper-left corner in (i,j)
int sq_ones(int i, int j, int s) {
return rect_ones(i, j, i + s - 1, j + s - 1);
}
int sq_zeros(int i, int j, int s) {
return rect_zeros(i, j, i + s - 1, j + s - 1);
}
int sq_change(int i, int j, int s) {
return rect_change(i, j, i + s - 1, j + s - 1);
}
// maxChangeRight[i][j][s] is the best improvement of score
// among squares in upper-left corner in (i,j) with size AT LEAST s
int maxChangeRight[][][];
int maxChangeLeft[][][]; // among squares with bottom-right corner in (i,j)
void precompute() {
pref_ones = new int[n + 1][n + 1];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
pref_ones[i][j] = input[i - 1][j - 1] + pref_ones[i - 1][j] +
pref_ones[i][j - 1] - pref_ones[i - 1][j - 1];
maxChangeRight = new int[n][n][n + 1];
maxChangeLeft = new int[n][n][n + 1];
for (int s = n; s >= 1; --s)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
maxChangeRight[i][j][s] = max(
s + max(i, j) <= n ? sq_change(i, j, s) : -INF,
s != n ? maxChangeRight[i][j][s + 1] : -INF);
maxChangeLeft[i][j][s] = max(
min(i, j) + 1 >= s ? sq_change(i - s + 1, j - s + 1, s) : -INF,
s != n ? maxChangeLeft[i][j][s + 1] : -INF);
}
}
int solveCornerRectangle() {
int ans = 0;
for (int x1 = 0; x1 < n; ++x1)
for (int x2 = x1; x2 < n; ++x2)
for (int y1 = 0; y1 < n; ++y1)
for (int y2 = y1; y2 < n; ++y2) {
int s = max(x2 - x1, y2 - y1) + 1; // minimum valid s
ans = max(ans, maxChangeRight[x1][y1][s] + maxChangeLeft[x2][y2][s] -
2 * rect_change(x1, y1, x2, y2));
}
return ans;
}
int solveInside() { // also considers using only one square
int ans = 0;
// worstChange[i][j][s] the biggest value of: improvement multiplied by -1
// among squares completely inside a square of size s with corner in (i,j)
int worstChange[][][] = new int[n + 1][n + 1][n + 1];
for (int s = 1; s <= n; ++s)
for (int i = 0; i < n; ++i)
for (int j = 0; s + max(i, j) <= n; ++j) {
worstChange[i][j][s] = max(max(max(max(worstChange[i][j][s - 1],
worstChange[i + 1][j][s - 1]), worstChange[i][j + 1][s - 1]),
worstChange[i + 1][j + 1][s - 1]), -sq_change(i, j, s));
ans = max(ans, sq_change(i, j, s) + worstChange[i][j][s]);
}
return ans;
}
int solveSeparate() {
int ans = 0;
int best_so_far = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
ans = max(ans, best_so_far + maxChangeRight[i][j][1]);
best_so_far = max(best_so_far, maxChangeLeft[i][j][1]);
}
return ans;
}
int solveMidRect() {
int ans = 0;
for (int x1 = 0; x1 < n; ++x1)
for (int y1 = 0; y1 < n; ++y1)
for (int y2 = y1; y2 < n; ++y2) {
int bestBigSq = -INF;
for (int y = 0; y <= y1; ++y)
bestBigSq = max(bestBigSq, maxChangeRight[x1][y][y2 - y + 1]);
int s_small = y2 - y1 + 1;
for (int x2 = x1; x2 < n; ++x2)
if (x2 - x1 < y2 - y1 && x2 - s_small + 1 >= 0)
ans = max(ans, bestBigSq + sq_change(x2 - s_small + 1, y1, s_small) -
2 * rect_change(x1, y1, x2, y2));
}
return ans;
}
public int maxOnes(String[] str) {
n = str.length;
input = new int[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
input[i][j] = str[i].charAt(j) - '0';
precompute();
int bestImprovement = solveInside();
for (int rep = 0; rep < 2; ++rep) {
bestImprovement = max(bestImprovement,
max(solveSeparate(), solveCornerRectangle()));
turn90();
precompute();
}
for (int rep = 0; rep < 4; ++rep) {
bestImprovement = max(bestImprovement, solveMidRect());
turn90();
precompute();
}
return bestImprovement + pref_ones[n][n];
}